﻿#define DEBUG_DRAW

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using PriorityQueue;
using System;
using System.Runtime.InteropServices;
using System.Linq;


namespace PathFinding
{
    public class JPSPathFinderCached : IPathFInder
    {

        //Debug Draw
        public List<Vector2Int> OpenedPoints { get; private set; }
        public List<Vector2Int> OtherClosedPoints { get; private set; }

        // end debug draw

        public List<Vector2Int> CurrentPath { get; private set; }

        /// <summary>
        /// 可以在单位行动时逐步处理
        /// </summary>
        public List<Vector2Int> SmoothedPath { get; private set; }

        PFGrid grid;

        struct JPSTile
        {

            public bool IsBlocked;
            public int LeftN, RightN, TopN, BottomN;
            public int TLN, TRN, BRN, BLN;
        }

        bool[,] closed;
        JPSTile[,] jpsTileCache;
        PFNode[,] nodes;
        PFNodeHeap openHeap;
        int mapXSize, mapYSize;

        public bool IsWorking { get; private set; }

        public JPSPathFinderCached(PFGrid pFGrid)
        {
            grid = pFGrid;
            mapXSize = grid.XSize;
            mapYSize = grid.YSize;

            closed = new bool[mapXSize, mapYSize];

            nodes = new PFNode[mapXSize, mapYSize];
            jpsTileCache = new JPSTile[mapXSize, mapYSize];
            for (int x = 0; x < mapXSize; ++x)
            {
                for (int y = 0; y < mapYSize; ++y)
                {
                    nodes[x, y] = new PFNode(new Vector2Int(x, y), grid[x, y]);
                }
            }

            IsWorking = false;

            // debug draw
            OpenedPoints = new List<Vector2Int>(1024);
            OtherClosedPoints = new List<Vector2Int>(1024);

        }

        private void CleanLocalList()
        {
            Array.Clear(closed, 0, closed.Length);
            CurrentPath = null;
            openHeap = null;
        }

        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
        private void SetClosed(in Vector2Int pos)
        {
            closed[pos.x, pos.y] = true;
        }

        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
        private bool IsClosed(in Vector2Int pos)
        {
            return closed[pos.x, pos.y];
        }

        public bool FindPath(Vector2Int start, Vector2Int goal, bool postSmooth = true)
        {
            if (IsWorking)
                throw new Exception("Can't init a new path finding now");
            if (jpsTileCache[start.x,start.y].IsBlocked || jpsTileCache[goal.x, goal.y].IsBlocked)
            {
                Debug.LogError("Invalid start point or goal point");
                return false;
            }

#if DEBUG_DRAW
            OpenedPoints.Clear();
            OtherClosedPoints.Clear();
#endif

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            IsWorking = true;
            CleanLocalList();

            openHeap = new PFNodeHeap();
            PFNode startNode = nodes[start.x, start.y];
            startNode.gCost = 0;
            startNode.hCost = PredictDistanceCost(start, goal);
            startNode.parent = null;
            //openHeap.Add(startNode);
            SetClosed(start);

#if DEBUG_DRAW
            OpenedPoints.Add(startNode.pos);
#endif
            JumpN(start, goal, start, false); // 向上
            JumpE(start, goal, start, false); // 向右
            JumpS(start, goal, start, false); // 向下
            JumpW(start, goal, start, false); // 向左

            JumpNE(start, goal); // 右上
            JumpNW(start, goal); // 左上
            JumpSE(start, goal); // 右下
            JumpSW(start, goal); // 左下

            while (openHeap.Count != 0)
            {
                PFNode nodeToVisit = openHeap.Pop();
                Vector2Int from = nodeToVisit.parent.pos;
                Vector2Int curr = nodeToVisit.pos;
                /// we found path
                if (curr == goal)
                {
                    sw.Stop();
                    Debug.Log("PathFind总共花费: " + sw.Elapsed.TotalMilliseconds + " ms");
#if DEBUG_DRAW
                    Debug.Log("Open: " + OpenedPoints.Count + " Closed: " + OtherClosedPoints.Count);
#endif

                    CurrentPath = new List<Vector2Int>(2);
                    while (nodeToVisit.pos != start && nodeToVisit.parent != null)
                    {
                        CurrentPath.Add(nodeToVisit.pos);
                        nodeToVisit = nodeToVisit.parent;
                    }
                    CurrentPath.Add(start);

                    CurrentPath.Reverse();

                    // post smooth
                    if (postSmooth)
                    {
                        System.Diagnostics.Stopwatch ssw = new System.Diagnostics.Stopwatch();
                        ssw.Start();

                        SmoothedPath = new List<Vector2Int>(2);

                        SmoothedPath.Add(CurrentPath.First());
                        var cs = CurrentPath[0];
                        for (var i = 1; i < CurrentPath.Count - 1; ++i)
                        {
                            if (!grid.IsLineOfSightJPS(cs, CurrentPath[i + 1]))
                            {
                                SmoothedPath.Add(CurrentPath[i]);
                                cs = CurrentPath[i];
                            }
                        }

                        SmoothedPath.Add(CurrentPath.Last());

                        ssw.Stop();
                        Debug.Log("Smooth总共花费: " + ssw.Elapsed.TotalMilliseconds + " ms");
                    }

                    IsWorking = false;
                    return true;
                }

                if (curr.x == from.x)
                {
                    if (curr.y < from.y)
                    {
                        JumpN(curr, goal, curr, false);

                        // _ c
                        // x F
                        if (curr.x - 1 >= 0 && !jpsTileCache[curr.x - 1, curr.y].IsBlocked && jpsTileCache[curr.x - 1, curr.y + 1].IsBlocked)
                        {
                            JumpW(curr, goal, curr, false);
                            JumpNW(curr, goal);
                        }

                        // c _
                        // F x
                        if (curr.x + 1 < mapXSize && !jpsTileCache[curr.x + 1, curr.y].IsBlocked && jpsTileCache[curr.x + 1, curr.y + 1].IsBlocked)
                        {
                            JumpE(curr, goal, curr, false);
                            JumpNE(curr, goal);
                        }
                    }
                    else
                    {
                        JumpS(curr, goal, curr, false);
                        // x F
                        // _ c
                        if (curr.x - 1 >= 0 && !jpsTileCache[curr.x - 1, curr.y].IsBlocked && jpsTileCache[curr.x - 1, curr.y - 1].IsBlocked)
                        {
                            JumpW(curr, goal, curr, false);
                            JumpSW(curr, goal);
                        }

                        // F x
                        // c _
                        if (curr.x + 1 < mapXSize && !jpsTileCache[curr.x + 1, curr.y].IsBlocked && jpsTileCache[curr.x + 1, curr.y - 1].IsBlocked)
                        {
                            JumpE(curr, goal, curr, false);
                            JumpSE(curr, goal);
                        }
                    }
                }
                else if (curr.x < from.x)
                {
                    if (curr.y == from.y)
                    {
                        JumpW(curr, goal, curr, false);
                        // _ x 
                        // c F 
                        if (curr.y - 1 >= 0 && !jpsTileCache[curr.x, curr.y - 1].IsBlocked && jpsTileCache[curr.x + 1, curr.y - 1].IsBlocked)
                        {
                            JumpN(curr, goal, curr, false);
                            JumpNW(curr, goal);
                        }

                        //  c F
                        //  _ x
                        if (curr.y + 1 < mapYSize && !jpsTileCache[curr.x, curr.y + 1].IsBlocked && jpsTileCache[curr.x + 1, curr.y + 1].IsBlocked)
                        {
                            JumpS(curr, goal, curr, false);
                            JumpSW(curr, goal);
                        }
                    }
                    else if (curr.y > from.y)
                    {
                        JumpSW(curr, goal);
                    }
                    else
                    {
                        JumpNW(curr, goal);
                    }
                }
                else
                {
                    if (curr.y == from.y)
                    {
                        JumpE(curr, goal, curr, false);
                        // x _
                        // F c
                        if (curr.y - 1 >= 0 && !jpsTileCache[curr.x, curr.y - 1].IsBlocked && jpsTileCache[curr.x - 1, curr.y - 1].IsBlocked)
                        {
                            JumpN(curr, goal, curr, false);
                            JumpNE(curr, goal);
                        }

                        // F c
                        // x _
                        if (curr.y + 1 < mapYSize && !jpsTileCache[curr.x, curr.y + 1].IsBlocked && jpsTileCache[curr.x - 1, curr.y + 1].IsBlocked)
                        {
                            JumpS(curr, goal, curr, false);
                            JumpSE(curr, goal);
                        }
                    }
                    else if (curr.y > from.y)
                    {
                        JumpSE(curr, goal);
                    }
                    else
                    {
                        JumpNE(curr, goal);
                    }
                }

                SetClosed(nodeToVisit.pos);
            }

            CurrentPath = null;
            SmoothedPath = null;
#if DEBUG_DRAW
            OpenedPoints.Clear();
            OtherClosedPoints.Clear();
            Debug.Log("Open: " + OpenedPoints.Count + " Closed: " + OtherClosedPoints.Count);
#endif
            IsWorking = false;

            sw.Stop();
            Debug.Log("PathFind总共花费: " + sw.Elapsed.TotalMilliseconds + " ms" + " 寻路失败");

            return false;
        }

        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
        private int DistCost(Vector2Int start, Vector2Int end)
        {
            int dx = Mathf.Abs(start.x - end.x);
            int dy = Mathf.Abs(start.y - end.y);

            return Mathf.Abs(dx - dy) * 10 + (dx > dy ? dy : dx) * 14;
        }

        /// <summary>
        /// 比g值计算方式略大，用以加速
        /// </summary>
        const int HValueMul = 10;
        /// <summary>
        /// 比g值计算方式略大，用以加速
        /// </summary>
        const int HValueMulDiagonal = 14;

        /// <summary>
        /// H 用于计算启发Cost 
        /// 即h值
        /// </summary>
        static int PredictDistanceCost(Vector2Int start, Vector2Int end)
        {
            //return Math.Abs(start.x - end.x) + Math.Abs(start.y - end.y); // 曼哈顿

            //return (int)((start - end).magnitude * 10); // 直线



            // 八向距离
            int dx = Mathf.Abs(start.x - end.x);
            int dy = Mathf.Abs(start.y - end.y);

            return Mathf.Abs(dx - dy) * HValueMul + (dx > dy ? dy : dx) * HValueMulDiagonal;

        }

        void TryAddOpenNode(in Vector2Int npos, in Vector2Int from, in Vector2Int goal)
        {
            if (IsClosed(npos))
                return;
            if (npos == from) // 有时有的节点的parent是自己，窝不太清楚发生了什么，但是必须避免这种情况
                return;

            var adjacent = nodes[npos.x, npos.y];

            PFNode fromNode = nodes[from.x, from.y];

            int toAdjacentCost = fromNode.gCost + DistCost(from, npos);
            if (!openHeap.Contains(adjacent) || toAdjacentCost < adjacent.gCost)
            {
                adjacent.gCost = toAdjacentCost;
                adjacent.hCost = PredictDistanceCost(npos, goal);
                adjacent.parent = fromNode;

                if (openHeap.Contains(adjacent))
                    openHeap.UpdateItem(adjacent);
                else
                {
#if DEBUG_DRAW
                    OpenedPoints.Add(adjacent.pos);
#endif
                    openHeap.Add(adjacent);
                }
            }
        }

        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
        public bool HasPointAt(in Vector2Int pos)
        {
            if (pos.x >= 0 && pos.x < mapXSize && pos.y >= 0 && pos.y < mapYSize)
                return true;
            return false;
        }

        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.AggressiveInlining)]
        public bool HasPointAt(int x, int y)
        {
            if (x >= 0 && x < mapXSize && y >= 0 && y < mapYSize)
                return true;
            return false;
        }


        /// <summary>
        /// 向北跳跃
        /// </summary>
        bool JumpN(in Vector2Int from, in Vector2Int goal, in Vector2Int fromParent, bool byDiagonal)
        {
            // 北方是障碍物
            if (jpsTileCache[from.x, from.y].TopN < 0)
            {
                // 目标在障碍物前面，我们可以抵达
                if (goal.x == from.x && goal.y <= from.y && goal.y >= Math.Abs(jpsTileCache[from.x, from.y].TopN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }


                return false;
            }
            else
            {
                // 目标在跳点前面，我们可以抵达
                if (goal.x == from.x && goal.y <= from.y && goal.y >= Math.Abs(jpsTileCache[from.x, from.y].TopN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }

                //if (closed[from.x, jpsNodes[from.x, from.y].TopN])
                //    return false;

                if (byDiagonal)
                    TryAddOpenNode(from, fromParent, goal);

                TryAddOpenNode(new Vector2Int(from.x, jpsTileCache[from.x, from.y].TopN), from, goal);

                //closed[from.x, jpsNodes[from.x, from.y].TopN] = true;


                return true;
            }
        }

        /// <summary>
        /// 向东跳跃
        /// </summary>
        bool JumpE(in Vector2Int from, in Vector2Int goal, in Vector2Int fromParent, bool byDiagonal)
        {
            // 东方是障碍物
            if (jpsTileCache[from.x, from.y].RightN < 0)
            {
                // 目标在障碍物前面，我们可以抵达
                if (goal.y == from.y && goal.x >= from.x && goal.x < Math.Abs(jpsTileCache[from.x, from.y].RightN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }


                return false;
            }
            else
            {
                // 目标在跳点前面，我们可以抵达
                if (goal.y == from.y && goal.x >= from.x && goal.x <= Math.Abs(jpsTileCache[from.x, from.y].RightN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }

                //if (closed[jpsNodes[from.x, from.y].RightN, from.y])
                //    return false;

                if (byDiagonal)
                    TryAddOpenNode(from, fromParent, goal);

                TryAddOpenNode(new Vector2Int(jpsTileCache[from.x, from.y].RightN, from.y), from, goal);

                //closed[jpsNodes[from.x, from.y].RightN, from.y] = true;

                return true;
            }
        }

        /// <summary>
        /// 向南跳跃
        /// </summary>
        bool JumpS(in Vector2Int from, in Vector2Int goal, in Vector2Int fromParent, bool byDiagonal)
        {
            // 南方是障碍物
            if (jpsTileCache[from.x, from.y].BottomN < 0)
            {
                // 目标在障碍物前面，我们可以抵达
                if (goal.x == from.x && goal.y >= from.y && goal.y < Math.Abs(jpsTileCache[from.x, from.y].BottomN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }


                return false;
            }
            else
            {
                // 目标在跳点前面，我们可以抵达
                if (goal.x == from.x && goal.y >= from.y && goal.y <= Math.Abs(jpsTileCache[from.x, from.y].BottomN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }

                //if (closed[from.x, jpsNodes[from.x, from.y].BottomN])
                //    return false;

                if (byDiagonal)
                    TryAddOpenNode(from, fromParent, goal);

                TryAddOpenNode(new Vector2Int(from.x, jpsTileCache[from.x, from.y].BottomN), from, goal);

                //closed[from.x, jpsNodes[from.x, from.y].BottomN] = true;

                return true;
            }

        }

        /// <summary>
        /// 向西跳跃
        /// </summary>
        bool JumpW(in Vector2Int from, in Vector2Int goal, in Vector2Int fromParent, bool byDiagonal)
        {
            // 西方是障碍物
            if (jpsTileCache[from.x, from.y].LeftN < 0)
            {
                // 目标在障碍物前面，我们可以抵达
                if (goal.y == from.y && goal.x <= from.x && goal.x >= Math.Abs(jpsTileCache[from.x, from.y].LeftN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }


                return false;
            }
            else
            {
                // 目标在跳点前面，我们可以直接抵达
                if (goal.y == from.y && goal.x <= from.x && goal.x >= Math.Abs(jpsTileCache[from.x, from.y].LeftN))
                {
                    if (byDiagonal)
                        TryAddOpenNode(from, fromParent, goal);

                    TryAddOpenNode(goal, from, goal);

                    return true;
                }

                //if (closed[jpsNodes[from.x, from.y].LeftN, from.y])
                //    return false;

                if (byDiagonal)
                    TryAddOpenNode(from, fromParent, goal);

                TryAddOpenNode(new Vector2Int(jpsTileCache[from.x, from.y].LeftN, from.y), from, goal);

                //closed[jpsNodes[from.x, from.y].LeftN, from.y] = true;


                return true;
            }
        }


        /// <summary>
        /// 向东北跳跃
        /// </summary>
        void JumpNE(in Vector2Int from, in Vector2Int goal)
        {
            if (goal.x - from.x == from.y - goal.y && from.y >= goal.y)
            {
                // 在跳点或障碍之前
                if (goal.x - from.x <= Math.Abs(jpsTileCache[from.x, from.y].TRN))
                {
                    TryAddOpenNode(goal, from, goal);
                    return;
                }
            }

            if (goal.x > from.x && goal.y < from.y)
            {
                int dist = Math.Abs(jpsTileCache[from.x, from.y].TRN);
                if (from.x + dist >= goal.x || from.y - dist <= goal.y)
                {
                    var jump = from;
                    for (int d = 0; d < dist; ++d)
                    {
                        ++jump.x; --jump.y;

                        //if (closed[jump.x, jump.y])
                        //    return;

                        bool HasOpenNode = false;
                        if (JumpN(jump, goal, from, true))
                            HasOpenNode = true;
                        if (JumpE(jump, goal, from, true))
                            HasOpenNode = true;

                        //if (!HasOpenNode)
                        //    closed[jump.x, jump.y] = true;
                        //else
                        //    return;

                        if (HasOpenNode)
                            return;
                    }
                }


            }
            
            if (jpsTileCache[from.x, from.y].TRN >= 0)
            {
                var jump = new Vector2Int(from.x + jpsTileCache[from.x, from.y].TRN, from.y - jpsTileCache[from.x, from.y].TRN);
                JumpN(jump, goal, from, true);
                JumpE(jump, goal, from, true);
            }
        }

        /// <summary>
        /// 向东南跳跃
        /// </summary>
        void JumpSE(in Vector2Int from, in Vector2Int goal)
        {
            if (goal.x - from.x == goal.y - from.y && goal.y >= from.y)
            {
                // 在跳点或障碍之前
                if (goal.x - from.x <= Math.Abs(jpsTileCache[from.x, from.y].BRN))
                {
                    TryAddOpenNode(goal, from, goal);
                    return;
                }
            }

            if (goal.x > from.x && goal.y > from.y)
            {
                int dist = Math.Abs(jpsTileCache[from.x, from.y].BRN);
                if (from.x + dist >= goal.x || from.y + dist >= goal.y)
                {
                    var jump = from;
                    for (int d = 0; d < dist; ++d)
                    {
                        ++jump.x; ++jump.y;

                        //if (closed[jump.x, jump.y])
                        //    return;

                        bool HasOpenNode = false;
                        if (JumpS(jump, goal, from, true))
                            HasOpenNode = true;
                        if (JumpE(jump, goal, from, true))
                            HasOpenNode = true;

                        //if (!HasOpenNode)
                        //    closed[jump.x, jump.y] = true;
                        //else
                        //    return;

                        if (HasOpenNode)
                            return;
                    }
                }
            }
            
            if (jpsTileCache[from.x, from.y].BRN >= 0)
            {
                var jump = new Vector2Int(from.x + jpsTileCache[from.x, from.y].BRN, from.y + jpsTileCache[from.x, from.y].BRN);
                JumpS(jump, goal, from, true);
                JumpE(jump, goal, from, true);
            }
        }

        /// <summary>
        /// 向西南跳跃
        /// </summary>
        void JumpSW(in Vector2Int from, in Vector2Int goal)
        {
            if (from.x - goal.x == goal.y - from.y && goal.y >= from.y)
            {
                // 在跳点或障碍之前
                if (from.x - goal.x <= Math.Abs(jpsTileCache[from.x, from.y].BLN))
                {
                    TryAddOpenNode(goal, from, goal);
                    return;
                }
            }
            if (goal.x < from.x && goal.y > from.y)
            {
                int dist = Math.Abs(jpsTileCache[from.x, from.y].BLN);

                if (from.x - dist <= goal.x || from.y + dist >= goal.y)
                {
                    var jump = from;
                    for (int d = 0; d < dist; ++d)
                    {
                        --jump.x; ++jump.y;

                        //if (closed[jump.x, jump.y])
                        //    return;

                        bool HasOpenNode = false;
                        if (JumpS(jump, goal, from, true))
                            HasOpenNode = true;
                        if (JumpW(jump, goal, from, true))
                            HasOpenNode = true;

                        //if (!HasOpenNode)
                        //    closed[jump.x, jump.y] = true;
                        //else
                        //    return;

                        if (HasOpenNode)
                            return;
                    }
                }
                    
            }
            
            if (jpsTileCache[from.x, from.y].BLN >= 0)
            {
                var jump = new Vector2Int(from.x - jpsTileCache[from.x, from.y].BLN, from.y + jpsTileCache[from.x, from.y].BLN);
                JumpS(jump, goal, from, true);
                JumpW(jump, goal, from, true);
            }
        }

        /// <summary>
        /// 向西北跳跃
        /// </summary>
        void JumpNW(in Vector2Int from, in Vector2Int goal)
        {
            if (from.x - goal.x == from.y - goal.y && from.y >= goal.y)
            {
                // 在跳点或障碍之前
                if (from.x - goal.x <= Math.Abs(jpsTileCache[from.x, from.y].TLN))
                {
                    TryAddOpenNode(goal, from, goal);
                    return;
                }
            }

            if (goal.x < from.x && goal.y < from.y)
            {
                int dist = Math.Abs(jpsTileCache[from.x, from.y].TLN);
                if (from.x - dist <= goal.x || from.y - dist <= goal.y)
                {
                    var jump = from;
                    for (int d = 0; d < dist; ++d)
                    {
                        --jump.x; --jump.y;

                        //if (closed[jump.x, jump.y])
                        //    return;

                        bool HasOpenNode = false;
                        if (JumpN(jump, goal, from, true))
                            HasOpenNode = true;
                        if (JumpW(jump, goal, from, true))
                            HasOpenNode = true;

                        //if (!HasOpenNode)
                        //    closed[jump.x, jump.y] = true;
                        //else
                        //    return;

                        if (HasOpenNode)
                            return;
                    }
                }
            }
            
            if (jpsTileCache[from.x, from.y].TLN >= 0)
            {
                var jump = new Vector2Int(from.x - jpsTileCache[from.x, from.y].TLN, from.y - jpsTileCache[from.x, from.y].TLN);
                JumpN(jump, goal, from, true);
                JumpW(jump, goal, from, true);
            }

        }

        void IPathFInder.UpdateMap()
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            for (int x = 0; x < mapXSize; ++x)
            {
                for (int y = 0; y < mapYSize; ++y)
                {
                    jpsTileCache[x, y].IsBlocked = grid[x, y].IsBlocked;
                }
            }


            for (int x = 0; x < mapXSize; ++x)
            {
                UpdateTopN(x);
                UpdateBottomN(x);
            }

            for (int y = 0; y < mapYSize; ++y)
            {
                UpdateLeftN(y);
                UpdateRightN(y);
            }

            for (int x = 0; x < mapXSize; ++x)
            {
                UpdateTLN(x, 0);
                UpdateTRN(x, 0);
                UpdateBLN(x, mapYSize - 1);
                UpdateBRN(x, mapYSize - 1);
            }

            for (int y = 0; y < mapYSize; ++y)
            {
                UpdateTLN(0, y);
                UpdateTRN(mapXSize - 1, y);
                UpdateBLN(0, y);
                UpdateBRN(mapXSize - 1, y);
            }


            sw.Stop();
            Debug.Log("UpdateMap总共花费: " + sw.Elapsed.TotalMilliseconds + " ms");
        }

        void UpdateRightN(int y)
        {
            int x = mapXSize;

            // 记录右侧的第一个特殊节点：负值为障碍物-index，正值和0为跳点
            // 注意到，障碍物节点记录的RightN如果为正值，可能是没有意义的，对应点不一定是跳点
            int xRightFirst = -mapXSize - 1;
            if (y == 0)
            {
                while (x > 1)
                {
                    --x;

                    jpsTileCache[x, y].RightN = xRightFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        xRightFirst = -x;
                    }
                    else if (jpsTileCache[x - 1, y + 1].IsBlocked && !jpsTileCache[x, y + 1].IsBlocked)
                    {
                        xRightFirst = x;
                    }
                }
            }
            else if (y == mapYSize - 1)
            {
                while (x > 1)
                {
                    --x;

                    jpsTileCache[x, y].RightN = xRightFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        xRightFirst = -x;
                    }
                    else if (jpsTileCache[x - 1, y - 1].IsBlocked && !jpsTileCache[x, y - 1].IsBlocked)
                    {
                        xRightFirst = x;
                    }
                }
            }
            else
            {
                while (x > 1)
                {
                    --x;

                    jpsTileCache[x, y].RightN = xRightFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        xRightFirst = -x;
                    }
                    else if ((jpsTileCache[x - 1, y + 1].IsBlocked && !jpsTileCache[x, y + 1].IsBlocked) ||
                        (jpsTileCache[x - 1, y - 1].IsBlocked && !jpsTileCache[x, y - 1].IsBlocked))
                    {
                        xRightFirst = x;
                    }
                }
            }

            jpsTileCache[0, y].RightN = xRightFirst;
        }

        void UpdateLeftN(int y)
        {
            int x = -1;

            // 记录左侧的第一个特殊节点：负值为障碍物-index - 1，正值和0为跳点
            int xLeftFirst = -1;
            if (y == 0)
            {
                while (x < mapXSize - 2)
                {
                    ++x;

                    jpsTileCache[x, y].LeftN = xLeftFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        xLeftFirst = -x - 1;
                    }
                    else if (jpsTileCache[x + 1, y + 1].IsBlocked && !jpsTileCache[x, y + 1].IsBlocked)
                    {
                        xLeftFirst = x;
                    }
                }
            }
            else if (y == mapYSize - 1)
            {
                while (x < mapXSize - 2)
                {
                    ++x;

                    jpsTileCache[x, y].LeftN = xLeftFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        xLeftFirst = -x - 1;
                    }
                    else if (jpsTileCache[x + 1, y - 1].IsBlocked && !jpsTileCache[x, y - 1].IsBlocked)
                    {
                        xLeftFirst = x;
                    }
                }
            }
            else
            {
                while (x < mapXSize - 2)
                {
                    ++x;

                    jpsTileCache[x, y].LeftN = xLeftFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        xLeftFirst = -x - 1;
                    }
                    else if ((jpsTileCache[x + 1, y + 1].IsBlocked && !jpsTileCache[x, y + 1].IsBlocked) ||
                        (jpsTileCache[x + 1, y - 1].IsBlocked && !jpsTileCache[x, y - 1].IsBlocked))
                    {
                        xLeftFirst = x;
                    }
                }
            }

            jpsTileCache[mapXSize - 1, y].LeftN = xLeftFirst;
        }

        void UpdateTopN(int x)
        {
            int y = -1;

            // 记录上方的第一个特殊节点：负值为障碍物-index - 1，正值和0为跳点
            int yTopFirst = -1;
            if (x == 0)
            {
                while (y < mapYSize - 2)
                {
                    ++y;

                    jpsTileCache[x, y].TopN = yTopFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        yTopFirst = -y - 1;
                    }
                    else if (jpsTileCache[x + 1, y + 1].IsBlocked && !jpsTileCache[x + 1, y].IsBlocked)
                    {
                        yTopFirst = y;
                    }
                }
            }
            else if (x == mapXSize - 1)
            {
                while (y < mapYSize - 2)
                {
                    ++y;

                    jpsTileCache[x, y].TopN = yTopFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        yTopFirst = -y - 1;
                    }
                    else if (jpsTileCache[x - 1, y + 1].IsBlocked && !jpsTileCache[x - 1, y].IsBlocked)
                    {
                        yTopFirst = y;
                    }
                }
            }
            else
            {
                while (y < mapYSize - 2)
                {
                    ++y;

                    jpsTileCache[x, y].TopN = yTopFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        yTopFirst = -y - 1;
                    }
                    else if ((jpsTileCache[x - 1, y + 1].IsBlocked && !jpsTileCache[x - 1, y].IsBlocked) ||
                         (jpsTileCache[x + 1, y + 1].IsBlocked && !jpsTileCache[x + 1, y].IsBlocked))
                    {
                        yTopFirst = y;
                    }
                }
            }

            jpsTileCache[x, mapYSize - 1].TopN = yTopFirst;
        }

        void UpdateBottomN(int x)
        {
            int y = mapYSize;

            // 记录下方的第一个特殊节点：负值为障碍物-index，正值和0为跳点
            int yBottomFirst = -mapYSize - 1;
            if (x == 0)
            {
                while (y > 1)
                {
                    --y;

                    jpsTileCache[x, y].BottomN = yBottomFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        yBottomFirst = -y;
                    }
                    else if (jpsTileCache[x + 1, y - 1].IsBlocked && !jpsTileCache[x + 1, y].IsBlocked)
                    {
                        yBottomFirst = y;
                    }
                }
            }
            else if (x == mapXSize - 1)
            {
                while (y > 1)
                {
                    --y;

                    jpsTileCache[x, y].BottomN = yBottomFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        yBottomFirst = -y;
                    }
                    else if (jpsTileCache[x - 1, y - 1].IsBlocked && !jpsTileCache[x - 1, y].IsBlocked)
                    {
                        yBottomFirst = y;
                    }
                }
            }
            else
            {
                while (y > 1)
                {
                    --y;

                    jpsTileCache[x, y].BottomN = yBottomFirst;

                    if (jpsTileCache[x, y].IsBlocked)
                    {
                        yBottomFirst = -y;
                    }
                    else if ((jpsTileCache[x + 1, y - 1].IsBlocked && !jpsTileCache[x + 1, y].IsBlocked) ||
                        (jpsTileCache[x - 1, y - 1].IsBlocked && !jpsTileCache[x - 1, y].IsBlocked))
                    {
                        yBottomFirst = y;
                    }
                }
            }

            jpsTileCache[x, 0].BottomN = yBottomFirst;
        }



        void UpdateTRN(int x, int y)
        {
            ++x; --y;

            int xFirst = x;
            bool firstIsObstacle = true;
            while (x > 0 && y < mapYSize - 1)
            {
                --x; ++y;
                if (firstIsObstacle)
                {
                    jpsTileCache[x, y].TRN = -(xFirst - x) + 1;
                }
                else
                {
                    jpsTileCache[x, y].TRN = (xFirst - x);
                }

                if (jpsTileCache[x, y].IsBlocked)
                {
                    xFirst = x;
                    firstIsObstacle = true;
                }
                else if (jpsTileCache[x, y].RightN >= 0 || jpsTileCache[x, y].TopN >= 0)
                {
                    // 这个节点水平延伸和垂直延伸方向有跳点，那么这个点也就是跳点
                    xFirst = x;
                    firstIsObstacle = false;
                }
            }
        }


        void UpdateTLN(int x, int y)
        {
            --x; --y;

            int xFirst = x;
            bool firstIsObstacle = true;
            while (x < mapXSize - 1 && y < mapYSize - 1)
            {
                ++x; ++y;
                if (firstIsObstacle)
                {
                    jpsTileCache[x, y].TLN = -(x - xFirst) + 1;
                }
                else
                {
                    jpsTileCache[x, y].TLN = x - xFirst;
                }

                if (jpsTileCache[x, y].IsBlocked)
                {
                    xFirst = x;
                    firstIsObstacle = true;
                }
                else if (jpsTileCache[x, y].LeftN >= 0 || jpsTileCache[x, y].TopN >= 0)
                {
                    // 这个节点水平延伸和垂直延伸方向有跳点，那么这个点也就是跳点
                    xFirst = x;
                    firstIsObstacle = false;
                }
            }
        }



        void UpdateBLN(int x, int y)
        {
            --x; ++y;
            int xFirst = x;
            bool firstIsObstacle = true;
            while (x < mapXSize - 1 && y > 0)
            {
                ++x; --y;
                if (firstIsObstacle)
                {
                    jpsTileCache[x, y].BLN = -(x - xFirst) + 1;
                }
                else
                {
                    jpsTileCache[x, y].BLN = x - xFirst;
                }

                if (jpsTileCache[x, y].IsBlocked)
                {
                    xFirst = x;
                    firstIsObstacle = true;
                }
                else if (jpsTileCache[x, y].LeftN >= 0 || jpsTileCache[x, y].BottomN >= 0)
                {
                    // 这个节点水平延伸和垂直延伸方向有跳点，那么这个点也就是跳点
                    xFirst = x;
                    firstIsObstacle = false;
                }
            }
        }


        void UpdateBRN(int x, int y)
        {
            ++x; ++y;
            int xFirst = x;
            bool firstIsObstacle = true;
            while (x > 0 && y > 0)
            {
                --x; --y;
                if (firstIsObstacle)
                {
                    jpsTileCache[x, y].BRN = -(xFirst - x) + 1;
                }
                else
                {
                    jpsTileCache[x, y].BRN = xFirst - x;
                }

                if (jpsTileCache[x, y].IsBlocked)
                {
                    xFirst = x;
                    firstIsObstacle = true;
                }
                else if (jpsTileCache[x, y].BottomN >= 0 || jpsTileCache[x, y].RightN >= 0)
                {
                    // 这个节点水平延伸和垂直延伸方向有跳点，那么这个点也就是跳点
                    xFirst = x;
                    firstIsObstacle = false;
                }
            }
        }

    }


}